package com.ohc.dp;

public class 斐波那契数列 {
    //    1 1 2  3  5  8  13  21
    public static void main(String[] args) {
        int n = 3;
        long start = System.currentTimeMillis();

        int digui = digui(30);
//        int digui = dynamic(20);
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start));
//        System.out.println("digui = " + digui);
    }

    public static int digui(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return digui(n - 1) + digui(n - 2);
    }

    public static int dynamic(int n) {
        int[] nums = new int[n];
        nums[0] = 1;
        nums[1] = 1;
        for (int i = 2; i < n; i++) {
            nums[i] = nums[i - 1] + nums[i - 2];
        }

        return nums[n - 1];
    }
}
